#include<bits/stdc++.h>
using namespace std;
long long Lcm(long long x,long long y)
{
	if(x == y) return 0;
	return x * y / __gcd(x,y);
}
const int n = 10000000;
int d[n+11],p[n+11],idx;
int a[111],b[111],topa,topb;
long long fa[111],fb[111];
int T;
long long x,y;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	for(int i = 2;i <= n;i++)
	{
		if(!d[i])
			d[i] = p[++idx] = i;
		for(int j = 1;j <= idx && i * p[j] <= n;j++)
		{
			d[i * p[j]] = d[i];
			if(p[j] == d[i])
				break;
		}
	}
	cin >> T;
	while(T--)
	{
		cin >> x >> y;
		long long ans = Lcm(x,y);
		a[topa = 1] = 2,b[topb = 1] = 2;
		int t = x;
		while(d[t])
		{
			if(d[t] != a[topa])
				a[++topa] = d[t];
			t /= d[t];
		}
		a[++topa] = x;
		t = y;
		while(d[t])
		{
			if(d[t] != b[topb])
				b[++topb] = d[t];
			t /= d[t];
		}
		b[++topb] = y;
		for(int i = 1;i <= topa;i++)
		{
			fa[i] = Lcm(x,a[i]);
			for(int j = 1;j <= topa;j++)
				fa[i] = min(fa[i],Lcm(x,a[j]) + Lcm(a[j],a[i]));
			ans = min(ans,fa[i] + Lcm(a[i],y));
		}
		for(int i = 1;i <= topb;i++)
		{
			fb[i] = Lcm(b[i],y);
			for(int j = 1;j <= topb;j++)
				fb[i] = min(fb[i],Lcm(b[i],b[j]) + Lcm(b[j],y));
			ans = min(ans,Lcm(x,b[i]) + fb[i]);
		}
		for(int i = 1;i <= topa;i++)
			for(int j = 1;j <= topb;j++)
				ans = min(ans,fa[i] + Lcm(a[i],b[j]) + fb[j]);
		cout << ans << "\n";
	}
	return 0;
}